package code;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Sum {
	
	public int mergeSort(int l,int r,int[] array){
		if(l==r){
			return 0;
		}
		int mid=l+r>>1;
		int lcnt=mergeSort(l,mid,array);
		int rcnt=mergeSort(mid+1,r,array);
		int sum=lcnt+rcnt;
		int[] tmp=new int[r-l+1];
		int idx=0;
		int i,j;
		for(i=l,j=mid+1;i<=mid && j<=r;){
			if(array[i]>array[j]){
				sum++;
				tmp[idx++]=array[j];
				j++;
			}
			else{
				tmp[idx++]=array[i];
				i++;
			}
		}
		for(;i<=mid;i++)	tmp[idx++]=array[i];
		for(;j<=r;j++)	tmp[idx++]=array[j];
		for(i=0;i<r-l+1;i++)
			array[l+i]=tmp[i];
		return sum;
	}
	public int binarySearch(int l,int r,int x,int[] num){
		int idx=-1,mid=0;
		while(l<=r){
			mid=l+r>>1;
			if(num[mid]==x)	return mid;
			if(num[mid]>x)	r=mid-1;
			else 
				l=mid+1;
		}
		return -1;
	}
    public List<List<Integer>> threeSum(int[] num) {
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        int n=num.length;
        if(n==0)	return result;
        
        mergeSort(0,n-1,num);
        
        int i,j,k;
//        Set<String> set=new HashSet<String>();
        for(i=0;i<n;i++){
        	if(i>0 && num[i]==num[i-1]) continue;
        	j=i+1;
        	k=n-1;
        	while(j<k){
        		if(j>i+1 && num[j]==num[j-1])	{
        			j++;
        			continue;
        		}
        		if(k!=j && k<n-1 && num[k]==num[k+1]) {
        			k--;
        			continue;
        		}
        		int sum=num[i]+num[j]+num[k];
        		if(sum>0)	k--;
        		else if(sum<0)	j++;
        		else{
	    			List<Integer> list=new ArrayList<Integer>();
	    			list.add(num[i]);
	    			list.add(num[j]);
	    			list.add(num[k]);
	    			result.add(list);
	    			j++;
        		}
        	}
        }
        for(i=0;i<result.size();i++){
        	for(j=0;j<result.get(i).size();j++)
        		System.out.print(result.get(i).get(j)+" ");
        	System.out.println();
        }
		return result;
    }
    
    public static void main(String[] args){
    	Sum sum=new Sum();
//    	int[] num={-1,0,1,2,-1,-4};
    	int[] num={0,0,0,1,2};
    	sum.threeSum(num);
    }
}
